package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.ListNode;
import com.zjw.algorithm.utils.TreeNode;

import java.util.Collection;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _合并k个有序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            ListNode h = list;
            while (h != null) {
                queue.offer(h);
                h = h.next;
            }
        }

        if (queue.isEmpty()) {
            return null;
        }

        ListNode node = queue.poll();
        ListNode head = node;
        while (!queue.isEmpty()) {
            ListNode nextPop = queue.poll();
            nextPop.next = null;
            node.next = nextPop;
            node = nextPop;
        }

        return head;
    }

    public ListNode sortList(ListNode head) {
        if (head == null){
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        ListNode p = head;
        while (p != null) {
            queue.offer(p);
            p = p.next;
        }

        ListNode node = queue.poll();
        ListNode newHead = node;
        while (!queue.isEmpty()) {
            ListNode nextPop = queue.poll();
            nextPop.next = null;
            node.next = nextPop;
            node = nextPop;
        }

        return newHead;
    }
}
